//
// Created by Administrator on 2021/11/13.
// May Saint Diana bless you!
//
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int singleNonDuplicate(vector<int> &nums) {
        int ans = 0;
        for (auto &x:nums) {
            ans ^= x;
        }
        return ans;
    }
};

class Solution2 {
public:
    int singleNonDuplicate(vector<int> &nums) {
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            bool halvesAreEven = (right - mid) % 2 == 0;  // 确定现在哪一侧元素个数为奇数
            if (nums[mid + 1] == nums[mid]) {
                if (halvesAreEven) {
                    left = mid + 2;
                } else {
                    right = mid - 1;
                }
            } else if (nums[mid - 1] == nums[mid]) {
                if (halvesAreEven) {
                    right = mid - 2;
                } else {
                    left = mid + 1;
                }
            } else {
                return nums[mid];
            }
        }
        return nums[left];
    }
};

class Solution3 {
public:
    int singleNonDuplicate(vector<int> &nums) {
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mid % 2 == 1) mid--; // 确保是偶数索引
            if (nums[mid] == nums[mid + 1]) { // 如果是成对的，那么偶数索引必然和其后的奇数索引构成一对
                left = mid + 2;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
};


int main() {
//    vector<int> nums{1, 1, 2, 3, 3, 4, 4, 8, 8};
//    vector<int> nums{3, 3, 7, 7, 10, 11, 11};
    vector<int> nums{1, 2, 2, 3, 3};
    Solution2 solution;
    cout << solution.singleNonDuplicate(nums) << endl;
    return 0;
}


